package swordoffer.offer10;

import java.util.HashMap;
import java.util.Map;

public class FibMemoRecursion {
    /**
     * 记忆化递归解法，将重复子问题记录，用到时直接获取结果
     */
    public int fib(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return fib(n, memo);
    }

    public int fib(int n, Map<Integer, Integer> memo) {
        if (n < 2) {
            return n;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int first = fib(n - 1, memo) % 1000000007;
        memo.put(n - 1, first);
        int second = fib(n - 2, memo) % 1000000007;
        memo.put(n - 2, second);
        int res = (first + second) % 1000000007;
        memo.put(n, res);
        return res;
    }
}
